#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=5*1e5+10;


vector<int> edge[N];
vector<int> edge2[N];
int w[N];
int st[N];
int dmax[N],dmin[N];
int n,m;
void spfa1(int dist[])
{
	
	queue<int> q;
	memset(st,0,sizeof(st));
	memset(dist,0x3f,sizeof(dmin));
	q.push(1);
	st[1]=1;
	dist[1]=w[1];

	while(q.size())
	{
		int r=q.front();
		st[r]=0;
		q.pop();
		for(int& e:edge[r])
		{
			if(dist[e]>min(dist[r],w[e]))
			{
				dist[e]=min(dist[r],w[e]);
				if(!st[e])
				{
					q.push(e);
					st[e]=1;
				}
			}

		}
	}
}
void spfa2()
{
	queue<int> q;
	memset(st,0,sizeof(st));
	memset(dmax,-0x3f,sizeof(dmax));
	q.push(n);
	st[n]=1;
	dmax[n]=w[n];
	
	while(q.size())
	{
		int r=q.front();
		st[r]=0;
		q.pop();
		for(int& e:edge2[r])
		{
			if(dmax[e]<max(dmax[r],w[e]))
			{
				dmax[e]=max(dmax[r],w[e]);
				if(!st[e])
				{
					q.push(e);
					st[e]=1;
				}
			}
		}

	}	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i];
		
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(z==1)
		{
			edge[x].push_back(y);
			edge2[y].push_back(x);
		}
		else{
			edge2[x].push_back(y);
			edge2[y].push_back(x);
			edge[x].push_back(y);
			edge[y].push_back(x);
		}
	}
	spfa1(dmin);
	spfa2();

	
	int ret=0;
	for(int i=1;i<=n;i++)
	{	
		ret=max(ret,dmax[i]-dmin[i]);
	}
	cout<<ret<<endl;
	return 0;
}
